#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <iomanip>

struct Point {
    double x, y;
    Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
    
    Point operator+(const Point& other) const {
        return Point(x + other.x, y + other.y);
    }
    
    Point operator-(const Point& other) const {
        return Point(x - other.x, y - other.y);
    }
    
    Point operator*(double scalar) const {
        return Point(x * scalar, y * scalar);
    }
    
    double norm() const {
        return std::sqrt(x * x + y * y);
    }
};

// 计算两条线的交点
Point* line_intersection(const Point& p1, const Point& p2, const Point& p3, const Point& p4) {
    double A1 = p2.y - p1.y;
    double B1 = p1.x - p2.x;
    double C1 = p1.x * p2.y - p2.x * p1.y;
    
    double A2 = p4.y - p3.y;
    double B2 = p3.x - p4.x;
    double C2 = p3.x * p4.y - p4.x * p3.y;
    
    double det = A1 * B2 - A2 * B1;
    
    if (std::abs(det) < 1e-10) {
        return nullptr;  // 平行线
    }
    
    double x = (B2 * C1 - B1 * C2) / det;
    double y = (A1 * C2 - A2 * C1) / det;
    
    return new Point(x, y);
}

// 计算所有切线交点
std::vector<Point> calculate_all_tangent_lines(const std::vector<Point>& centers, double radius) {
    std::vector<Point> intersection_points;
    
    for (size_t i = 1; i < centers.size() - 1; i++) {
        const Point& p1 = centers[i - 1];
        const Point& p2 = centers[i];
        const Point& p3 = centers[i + 1];
        
        // 计算切线与圆心连线的夹角
        double angle1 = std::atan2(p2.y - p1.y, p2.x - p1.x);
        double angle2 = std::atan2(p3.y - p2.y, p3.x - p2.x);
        
        // 计算切线的斜率
        double slope1 = angle1;
        double slope2 = angle2;
        
        // 计算第一个圆与第二个圆的切线点
        Point t1_up(p1.x + radius * std::sin(slope1), p1.y - radius * std::cos(slope1));
        Point t2_up(p2.x + radius * std::sin(slope1), p2.y - radius * std::cos(slope1));
        
        Point t1_down(p1.x - radius * std::sin(slope1), p1.y + radius * std::cos(slope1));
        Point t2_down(p2.x - radius * std::sin(slope1), p2.y + radius * std::cos(slope1));
        
        // 计算第二个圆与第三个圆的切线点
        Point t3_up(p2.x + radius * std::sin(slope2), p2.y - radius * std::cos(slope2));
        Point t4_up(p3.x + radius * std::sin(slope2), p3.y - radius * std::cos(slope2));
        
        Point t3_down(p2.x - radius * std::sin(slope2), p2.y + radius * std::cos(slope2));
        Point t4_down(p3.x - radius * std::sin(slope2), p3.y + radius * std::cos(slope2));
        
        // 检查切线是否平行
        if (std::abs(slope1 - slope2) > 1e-6) {  // 不平行
            Point* intersection = line_intersection(t1_up, t2_up, t3_up, t4_up);
            if (intersection != nullptr) {
                intersection_points.push_back(*intersection);
                delete intersection;
            }
            
            intersection = line_intersection(t1_down, t2_down, t3_down, t4_down);
            if (intersection != nullptr) {
                intersection_points.push_back(*intersection);
                delete intersection;
            }
        } else {
            // 两条切线平行，需要计算中间圆与切线的两个交点
            Point intersection1(p2.x + radius * std::sin(slope1), p2.y - radius * std::cos(slope1));
            Point intersection2(p2.x - radius * std::sin(slope1), p2.y + radius * std::cos(slope1));
            intersection_points.push_back(intersection1);
            intersection_points.push_back(intersection2);
        }
    }
    
    return intersection_points;
}

// 过滤距离圆心太近的点
std::pair<std::vector<Point>, std::vector<Point>> filter_points_near_centers(
    const std::vector<Point>& points, 
    const std::vector<Point>& centers, 
    double radius) {
    
    std::vector<Point> filtered_points;
    std::vector<Point> outline_points;
    
    for (const auto& point : points) {
        bool far_enough = true;
        for (const auto& center : centers) {
            Point diff = point - center;
            if (diff.norm() < radius) {
                far_enough = false;
                break;
            }
        }
        
        if (far_enough) {
            filtered_points.push_back(point);
        } else {
            outline_points.push_back(point);
        }
    }
    
    return std::make_pair(filtered_points, outline_points);
}

// 在点之间按照给定密度补点
std::vector<Point> add_inbetween_points(const std::vector<Point>& points, double density) {
    std::vector<Point> new_points;
    
    for (size_t i = 0; i < points.size() - 1; i++) {
        new_points.push_back(points[i]);
        
        Point point1 = points[i];
        Point point2 = points[i + 1];
        Point diff = point2 - point1;
        double dist = diff.norm();
        
        if (dist > density * 2) {
            // 计算应该补充多少点
            int num_points_to_add = static_cast<int>(std::ceil(dist / density)) - 1;
            
            for (int j = 1; j <= num_points_to_add; j++) {
                double ratio = static_cast<double>(j) / (num_points_to_add + 1);
                Point new_point = point1 + diff * ratio;
                new_points.push_back(new_point);
            }
        }
    }
    
    new_points.push_back(points.back());  // 添加最后一个点
    return new_points;
}

// 从文件加载数据
std::vector<Point> load_data(const std::string& file_name) {
    std::vector<Point> data;
    std::ifstream file(file_name);
    std::string line;
    
    while (std::getline(file, line)) {
        // 去除空格和括号
        std::string clean_line = line;
        clean_line.erase(std::remove(clean_line.begin(), clean_line.end(), ' '), clean_line.end());
        clean_line.erase(std::remove(clean_line.begin(), clean_line.end(), '('), clean_line.end());
        clean_line.erase(std::remove(clean_line.begin(), clean_line.end(), ')'), clean_line.end());
        
        if (clean_line.empty()) continue;
        
        std::stringstream ss(clean_line);
        std::string x_str, y_str;
        
        if (std::getline(ss, x_str, ',') && std::getline(ss, y_str)) {
            try {
                double x = std::stod(x_str);
                double y = std::stod(y_str);
                data.push_back(Point(x, y));
            } catch (const std::exception& e) {
                std::cerr << "Error parsing line: " << line << std::endl;
            }
        }
    }
    
    return data;
}

// 保存点集到文件
void save_points(const std::vector<Point>& points, const std::string& filename) {
    std::ofstream file(filename);
    file << std::fixed << std::setprecision(6);
    for (const auto& point : points) {
        file << point.x << "," << point.y << "\n";
    }
    file.close();
}

int main() {
    // 加载数据
    std::vector<Point> data = load_data("../data.txt");
    
    if (data.empty()) {
        std::cerr << "Error: No data loaded from data.txt" << std::endl;
        return 1;
    }
    
    std::cout << "Loaded " << data.size() << " points from data.txt" << std::endl;
    
    // 使用calculate_all_tangent_lines函数计算交点
    std::vector<Point> intersection_points = calculate_all_tangent_lines(data, 1.0);
    
    // 分割为外圈和内圈
    std::vector<Point> outside_points;
    std::vector<Point> inside_points;
    
    for (size_t i = 0; i < intersection_points.size(); i++) {
        if (i % 2 == 0) {
            inside_points.push_back(intersection_points[i]);
        } else {
            outside_points.push_back(intersection_points[i]);
        }
    }
    
    // 过滤距离原始点小于radius的点
    auto [filtered_outside_points, out_duo] = filter_points_near_centers(outside_points, data, 1.0);
    auto [filtered_inside_points, in_duo] = filter_points_near_centers(inside_points, data, 1.0);
    
    // 计算原始点之间的平均距离，用作补点的密度
    double total_distance = 0.0;
    for (size_t i = 0; i < data.size() - 1; i++) {
        Point diff = data[i + 1] - data[i];
        total_distance += diff.norm();
    }
    double average_distance = total_distance / (data.size() - 1);
    
    std::cout << "Average distance: " << average_distance << std::endl;
    
    // 对过滤后的外圈和内圈进行补点
    std::vector<Point> supplemented_outside_points = add_inbetween_points(filtered_outside_points, average_distance);
    std::vector<Point> supplemented_inside_points = add_inbetween_points(filtered_inside_points, average_distance);
    
    std::cout << "Inside points count: " << supplemented_inside_points.size() << std::endl;
    std::cout << "Outside points count: " << supplemented_outside_points.size() << std::endl;
    
    // 保存结果到文件
    save_points(data, "original_points.txt");
    save_points(supplemented_outside_points, "outside_points.txt");
    save_points(supplemented_inside_points, "inside_points.txt");
    
    std::cout << "Results saved to:" << std::endl;
    std::cout << "  - original_points.txt" << std::endl;
    std::cout << "  - outside_points.txt" << std::endl;
    std::cout << "  - inside_points.txt" << std::endl;
    
    return 0;
}

